package leetcode.editor.cn;

//给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
//
// 有效字符串需满足：
//
//
// 左括号必须用相同类型的右括号闭合。
// 左括号必须以正确的顺序闭合。
// 每个右括号都有一个对应的相同类型的左括号。
//
//
//
//
// 示例 1：
//
//
//输入：s = "()"
//输出：true
//
//
// 示例 2：
//
//
//输入：s = "()[]{}"
//输出：true
//
//
// 示例 3：
//
//
//输入：s = "(]"
//输出：false
//
//
//
//
// 提示：
//
//
// 1 <= s.length <= 10⁴
// s 仅由括号 '()[]{}' 组成
//
//
// Related Topics 栈 字符串 👍 3677 👎 0

import com.sun.xml.internal.messaging.saaj.util.CharReader;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

class ValidParentheses{
    public static void main(String[] args) {

        Solution solution = new ValidParentheses().new Solution();
        boolean valid = solution.isValid("([])");
        System.out.println(valid);
    }

    /**
     * 1,创建for循环遍历字符串
     *      取字符串的每个字符
     *      如果是左括号就保存在栈里面
     *      如果是右括号这些就和栈顶元素匹配
     *      如果匹配不上就返回false
     * 2,检查栈是否为空
     */
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean isValid(String s) {
        Map<Character, Character> map = new HashMap<Character,Character>();
        map.put(')','(');
        map.put('}','{');
        map.put(']','[');
        Stack stack=new Stack();
        for (int i = 0; i < s.length(); i++) {
            char c=s.charAt(i);
            if(map.containsValue(c)){
                stack.push(c);

            }else if (map.containsKey(c)){
                if(!stack.isEmpty()&&stack.peek()==map.get(c)){
                    stack.pop();
                }else{
                    return  false;
                }

            }else{
                return false;
            }

        }
        if(stack.isEmpty()){
            return true;
        }
            return false;

    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
